翻訳と辞書 Words near each other ・ Ring homomorphism ・ Ring I ・ Ring II ・ Ring II of Ringerike ・ Ring III ・ Ring It Up! ・ Ring Ka King ・ Ring King ・ Ring Knutstorp ・ Ring languages ・ Ring Lardner ・ Ring Lardner, Jr. ・ Ring laser ・ Ring laser gyroscope ・ Ring latency ・ Ring Learning with Errors ・ Ring learning with errors key exchange ・ Ring learning with errors signature ・ Ring Line (Oslo) ・ Ring Magazine comeback of the year ・ Ring Magazine event of the year ・ Ring magazine Fight of the Year ・ Ring magazine Fighter of the Year ・ Ring Magazine hall of fame ・ Ring magazine Knockout of the Year ・ Ring Magazine pound for pound ・ Ring Magazine progress of the year ・ Ring Magazine prospect of the year ・ Ring Magazine round of the year ・ Ring Magazine upsets of the year Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Ring Learning with Errors ： ウィキペディア英語版 Ring Learning with Errors Ring Learning with Errors (RLWE) is a computational problem which serves as the foundation of new cryptographic algorithms designed to protect against cryptanalysis by quantum computers and also to provide the basis for homomorphic encryption. RLWE is more properly called Learning with Errors over Rings and is simply the larger Learning with Errors problem specialized to polynomial rings over finite fields.〔 Because of the presumed difficulty of solving the RLWE problem even on a quantum computer, RLWE based cryptography may form the fundamental base for public key cryptography in the future just as the integer factorization and discrete logarithm problem have served as the base for public key cryptography since the early 1980s. An important feature of basing cryptography on the Ring Learning with Errors problem is the fact that the solution to the RLWE problem may be reducible to the NP-Hard Shortest Vector Problem (SVP) in a Lattice.〔 == Background == The security of modern cryptography, in particular Public Key Cryptography, is based on the difficulty of solving computational problems believed to be intractable if the size of the problem is large enough and the instance of the problem to be solved is chosen randomly. The classic example that has been used since the 1970s is the integer factorization problem. It is believed that it is computationally intractable to factor the product of two prime numbers if those prime numbers are large enough and chosen at random. As of 2015 research has led to the factorization of the product of two 384-bit primes but not the product of two 512-bit primes. Integer factorization forms the basis of the widely used RSA cryptographic algorithm. The Ring Learning with Errors (RLWE) problem is built on the arithmetic of polynomials with coefficients from a finite field.〔 A typical polynomial a(x) is expressed as: $a(x)\; =\; a\_0\; +\; a\_1x\; +\; a\_2x^2\; +\; ...\; +\; a\_x^\; +\; a\_x^$ Polynomials can be added and multiplied in the usual fashion. In the RLWE context the coefficients of the polynomials and all operations involving those coefficients will be done in a finite field, typically the field $Z/qZ\; =\; F\_q$ for a prime integer $q$. The set of polynomials over a finite field with the operations of addition and multiplication forms an infinite polynomial ring ($F\_q()$). The RLWE context works with a finite sub-ring of this infinite ring. The sub-ring is typically the finite quotient (factor) ring formed by reducing all of the polynomials in $F\_q()$ modulo an irreducible polynomial $\backslash Phi(x)$. This finite quotient ring can be written as $F\_q()/\backslash Phi(x)$ though many authors write $Z\_q()/\backslash Phi(x)$ .〔 If the degree polynomial $\backslash Phi(x)$ is n, the sub-ring becomes the ring of polynomials of degree less than n modulo $\backslash Phi(x)$ with coefficients from $F\_q$. The values n, q, together with the polynomial $\backslash Phi(x)$ partially define the mathematical context for the RLWE problem. Another concept necessary for the RLWE problem is the idea of "small" polynomials with respect to some norm. The typical norm used in the RLWE problem is known as the infinity norm. The infinity norm of a polynomial is simply the largest coefficient of the polynomial when these coefficients are viewed as integers. Hence, $||a(x)||\_\backslash infty\; =\; b$ states that the infinity norm of the polynomial $a(x)$ is $b$. Thus $b$ is the largest coefficient of $a(x)$. The final concept necessary to understand the RLWE problem is the generation of random polynomials in $Z\_q()/\backslash Phi(x)$ and the generation of "small" polynomials . A random polynomial is easily generated by simply randomly sampling the n coefficients of the polynomial from $F\_q$ where $F\_q$ is typically represented as the set:$(-(q-1)/2,\; ...,\; -1,\; 0,\; 1,\; ...,\; (q-1)/2)$. Randomly generating a "small" polynomial done by generating the coefficients of the polynomial from $F\_q$ in a way that either guarantees or makes very likely small coefficients. There are two common ways to do this: # Using Uniform Sampling - The coefficients of the small polynomial are uniformly sampled from a set of small coefficients. Let b be an integer that is much less than q. If we randomly choose coefficients from the set: the polynomial will be small with respect to the bound (b). # Using Discrete Gaussian Sampling - For an odd value for q, the coefficients of the polynomial are randomly chosen by sampling from the set according to a discrete Gaussian distribution with mean 0 and distribution parameter σ. The references describe in full detail how this can be accomplished. It is more complicated than uniform sampling but it allows for a proof of security of the algorithm. The paper, "Sampling from Discrete Gaussians for Lattice-Based Cryptography on a Constrained Device," by Dwarakanath and Galbraith provide an overview of this problem. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Ring Learning with Errors」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.